package Time_13;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-04-10
 * Time:14:07
 * Text：带权最短路路径
 */
class graph2{
    private char[] vertexts; //存放顶点
    private int[][] matrix; //拓扑图
    private int[] shortSize; // 最短路径
    int[] bool;
    private HashMap<Character,Integer> t1;

    public graph2(char[] vertexts, int[][] matrix) {
        this.vertexts = vertexts;
        this.matrix = matrix;
        this.bool = new int[vertexts.length];
        shortSize = new int[vertexts.length];
        Arrays.fill(shortSize,Integer.MAX_VALUE);
        t1 = new HashMap<>();
        for(int i=0;i< vertexts.length;i++){
            t1.put(vertexts[i],i);
        }
    }
    public int shortRoad(char start,char end){
        int s = t1.get(start);
        int endNum = t1.get(end);
        shortSize[s] = 0;
        Queue<Integer> t1= new LinkedList<>();
        t1.add(s);
        while(!t1.isEmpty()){
            int q = t1.poll();
            for(int i = 0;i < matrix[q].length ;i++){
                if(matrix[q][i] ==0 || bool[i] ==1){
                    continue;
                }else{
                    //计算当前值
                    int numT = shortSize[q] + matrix[q][i];
                    shortSize[i] = Math.min(shortSize[i],numT);
                    if(!t1.contains(i)){
                        t1.add(i);
                    }
                }
            }
            bool[q]=1;
        }
        return shortSize[endNum];

    }
}
public class Test2 {

    public static void main(String[] args) {
        char[] array={'a','b','c','d','e','f','g'};
        int max=0;
        int[][] arr = {
                {0,3,4,max,max,max,max},
                {3,0,7,max,2,max,5},
                {4,7,0,max,max,8,max},
                {max,max,max,0,19,2,max},
                {max,2,max,19,0,max,max},
                {max,max,8,2,max,max,max},
                {max,5,max,max,max,max,0}
        };
        System.out.println( new graph2(array,arr).shortRoad('b','d'));

    }
}
